package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/make-costs-of-paths-equal-in-a-binary-tree/'>使二叉树所有路径值相等的最小代价(Make Costs of Paths Equal in a Binary Tree)</a>
 * <p>给你一个整数 n 表示一棵 满二叉树 里面节点的数目，节点编号从 1 到 n 。根节点编号为 1 ，树中每个非叶子节点 i 都有两个孩子，分别是左孩子 2 * i 和右孩子 2 * i + 1 。</p>
 *
 * <p>树中每个节点都有一个值，用下标从 0 开始、长度为 n 的整数数组 cost 表示，其中 cost[i] 是第 i + 1 个节点的值。每次操作，你可以将树中 任意 节点的值 增加 1 。你可以执行操作 任意 次。</p>
 *
 * <p>你的目标是让根到每一个 叶子结点 的路径值相等。请你返回 最少 需要执行增加操作多少次。</p>
 *
 * <p>
 * 注意：
 *     <ul>
 *         <li>满二叉树 指的是一棵树，它满足树中除了叶子节点外每个节点都恰好有 2 个子节点，且所有叶子节点距离根节点距离相同。</li>
 *         <li>路径值 指的是路径上所有节点的值之和。</li>
 *     </ul>
 * </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：n = 7, cost = [1,5,2,2,3,3,1]
 *      输出：6
 *      解释：我们执行以下的增加操作：
 *          - 将节点 4 的值增加一次。
 *          - 将节点 3 的值增加三次。
 *          - 将节点 7 的值增加两次。
 *          从根到叶子的每一条路径值都为 9 。
 *          总共增加次数为 1 + 3 + 2 = 6 。
 *          这是最小的答案。
 *
 * 示例 2：
 *      输入：n = 3, cost = [5,3,3]
 *      输出：0
 *      解释：两条路径已经有相等的路径值，所以不需要执行任何增加操作。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>3 <= n <= 10^5</li>
 *     <li>n + 1 是 2 的幂</li>
 *     <li>cost.length == n</li>
 *     <li>1 <= cost[i] <= 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/2/28 13:38
 */
public class LC2673MakeCostsOfPathsEqualInBinaryTree_M {

    static class Solution {


        public int minIncrements(int n, int[] cost) {
            /*
                         1                      1                     11
                       /   \                  /   \                  /  \
                      2     3       ==》     7     10        ==>   10     10     (5-4)  + (7-6)  + (10-7)
                     / \   / \             /  \   /  \            / \    / \
                    4   5 6   7           5    5 7    7          5   5  7   7

             */
            int ans = 0;
            for (int i = n - 2; i > 0; i -= 2) {
                // cost[i]左子节点；cost[i + 1]右子节点。让左右子节点的值操作最少次数后相等。
                ans += Math.abs(cost[i] - cost[i + 1]);
                // cost[i / 2]父节点。父节点的值加上，相等后的值
                cost[i / 2] += Math.max(cost[i], cost[i + 1]);
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minIncrements(7, new int[]{1, 5, 2, 2, 3, 3, 1}));
        System.out.println(solution.minIncrements(3, new int[]{5, 3, 3}));
        System.out.println(solution.minIncrements(15, new int[]{764, 1460, 2664, 764, 2725, 4556, 5305, 8829, 5064, 5929, 7660, 6321, 4830, 7055, 3761}));
        System.out.println(solution.minIncrements(7, new int[]{1, 2, 3, 4, 5, 6, 7}));
    }
}
